Modern day data communications is accomplished by transferring bits (0's and 1's) between two communicating devices. These bits are usually segmented into units called packets and routed through a communications network. The packets are routed through the network by switching devices (queue servers), which process the packets and send them along different communications pathways to their final destination.
Packets often line up at a queue server waiting to be serviced by the queue server in the same way that a line at a bank might develop in front of a teller. The line is referred to as a queue. The packets would be the people in the queue and the teller would be the switch or queue server. However not all packets are the same size. Often a shorter packet that could be quickly processed by the queue server waits in the queue while a longer packet is serviced. As a result, the communicating parties at the end are delayed until a large packet that has nothing to do with their particular communication, is processed. Ultimately many different parties that are communicating through the switch (or queue server) would be slowed down, while the queue server processes a large packet that has nothing to do with their respective communications sessions.
It would be advantageous to service smaller length packets, located behind larger packets in the queue, without waiting for the large packets to be fully processed. Attempts have been made to design simple architectures that solve this queuing problem. Software scheduling techniques have been devised which increase the equity in processing the packets by examining the entire queue of packets. However, it is difficult to devise a high-speed and memory-efficient hardware implementation of this method, as needed by Asynchronous Transfer Mode (ATM) switches, or high speed queue servers. At least one fast implementation was attempted in an ATM switch. However, the method required complex manipulations of the pointers that identified the different packets. As a result, these methods required multiple read and write commands to the memory of the switch, which in turn help to make method slow to implement. Therefore, it would be advantageous to develop a simple hardware technique for reducing queuing delays that could be performed in Real-Time.